Involuntary weight loss or wasting indicative of severe protein energy malnutrition is a frequent complication of AIDS. Since wasting associated w/AIDS is characterized by a loss of muscle mass, and because the prognosis for pts. with AIDS worsens with the loss of fat free mass, we hypothesize that a program of progressive resistance and aerobic exercise prescribed in combination with megestrol acetate will result in greater increases in lean body mass than either intervention alone for pts. w/ AIDS-related weight loss.